/**
 * 功能：根据城市间的连接信息，找出start到target的所有可能的路径
 * @author majx 
 */

var Weight = function (price, pathLength) {
    this.price = price;
    this.pathLength = pathLength;
};

var Road = function (path, len, price) {
    this.path = path.slice(0);
    this.len = len;
    this.price = price;
};

var PathsSourceTarget = (graph, start, target) => {
    let paths = [];
    let road = new Road([], 0, 0);
    let visited = new Array(graph.length).fill(0);

    let travelGraph = (vertex, target, road, visited, price, len) => {
		// if(paths.length == 25){ 
		// 	return ;
		// }
		
	  if (vertex == target) {
        visited[vertex] = 1;

        road.path.push(vertex);
        road.len += len;
        road.price += price;
        paths.push(road);

        return;
      }
	
	// console.log("当前所记录的路径",paths);
      visited[vertex] = 1;
      road.path.push(vertex);
      road.len += len;
      road.price += price;

      for (let i = 0; i < graph.length; i++) {
        if (visited[i] == 0 && graph[vertex][i].pathLength != -1) {
            let visTemp = visited.slice(0);
            let roadTemp = new Road(road.path,road.len,road.price);
            travelGraph(
            i,
            target,
            roadTemp,
            visTemp,
            graph[vertex][i].price,
            graph[vertex][i].pathLength
          );
        }
      }

      return;
    };

    travelGraph(start, target, road, visited, 0, 0);
    return paths;
};
module.exports.Weight = Weight;
module.exports.PathsSourceTarget = PathsSourceTarget;